//
//  ProblemOffer57.swift
//  TestProject
//
//  Created by 武侠 on 2021/7/12.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 剑指 Offer 57. 和为s的两个数字 ✅
 输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

 示例 1：
     输入：nums = [2,7,11,15], target = 9
     输出：[2,7] 或者 [7,2]
 示例 2：
     输入：nums = [10,26,30,31,47,60], target = 40
     输出：[10,30] 或者 [30,10]
 限制：
 1 <= nums.length <= 10^5
 1 <= nums[i] <= 10^6

 */
@objcMembers class ProblemOffer57: NSObject {
    func solution() {
        print(twoSum([2,7,11,15], 9))
        
        print(twoSum([10,26,30,31,47,60], 40))
    }
    
    /*
     双向指针：
     1: 定义左指针left = 0，右指针right = count-1
     2: 求和sum = nums[left] + nums[right], 判断sum与target的关系
        sum == target 找到了
        sum > target  那么让left右移动一下
        sum < target  那么让right左移动一下
     */
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var l = 0, r = nums.count-1
        var t = 0
        while l < r {
            t = nums[l] + nums[r]
            if t > target {
                r -= 1
            } else if t < target {
                l += 1
            } else {
                return [nums[l], nums[r]]
            }
        }
        return []
    }
}
